#define R return
#define S(z) scanf("%d",&z)
typedef int I;I m[100][100],r;I d(I i,I j){I a,b;if(i==r)R 0;a=d(i+1,j+1);b=d(i+1,j);R m[i][j]+(a>b?a:b);}I main(){I i,j,t;s(t);for(;t--;){s(r);for(i=0;i<r;i++)for(j=0;j<i+1;j++)s(m[i][j]);printf("%d\n",d(0,0));}R 0;}
